package dp.子数组;

import java.util.Arrays;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N最长回文子串5.java
 * @Description https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @createTime 2021年10月25日 20:46:00
 */
public class 最长回文子串5 {

	public String longestPalindrome(String s) {
		int length=s.length();

		//如果长度小于2，肯定是回文串
		if (length<2) {
			return s;
		}

		//回文串转换为数字
		char[] chars = s.toCharArray();

		//DP[i][j] 表示对应的值是字符串 i....j是否是回文串
		boolean[][] dp=new boolean[length][length];


		//-------状态初始化---------//
		//当i=j的时候，一定是回文子串
		for (int i = 0; i < length; i++) {
			dp[i][i]=true;
		}

		int maxLen = 1;
		int begin = 0;

		//--------转态转移方程-----------//
		//遍历字符串到位置j
		for (int j = 1; j < length; j++) {
			//遍历字符串从i 到 j
			for (int i = 0; i < j; i++) {
				//转态1：如果i j 位置字符串不相等，那么dp[i][j]=false
				if (chars[i]!=chars[j]){
					dp[i][j]=false;
				}else {
					/**
					 * 状态2 如果i j 位置字符串相等，那么dp[i][j]=dp[i+1][j-1]
					 * 如果 i 和j的中间字符串小于3，并且i=j，那么必定是回文串
					 */
					if (j-i<3){
						dp[i][j]=true;
					}else {
						dp[i][j]=dp[i+1][j-1];
					}
				}

				// 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
				if (dp[i][j] && j - i + 1 > maxLen) {
					maxLen = j - i + 1;
					begin = i;
				}
			}
		}
		return s.substring(begin, begin + maxLen);
	}
}
